BZOJ4361 isn <容斥+DP+线段树优化>

Problem

isn

Description

给出一个长度为的序列。如果序列不是非降的，你必须从中删去一个数，重复这一操作，直到非降为止。求有多少种不同的操作方案，答案模。

Input

第一行一个整数。
接下来一行个整数，描述。

Output

一行一个整数，描述答案。

Sample Input

1
2

4
1 7 5 3

Sample Output

Hint

标签：容斥 DP 线段树

Solution

用表示以结尾长度为的不下降子序列个数，则

这个是的，可以用线段树优化到。

用表示长为的不下降子序列个数，则

令为最后留下的不下降序列长度为的可行方案数，那么显然有，考虑如何通过计算。
如果不考虑方案是否可行，则留下的序列有种选法，删除个数有种顺序，于是所有方案（不论是否可行）的数量为。
从所有方案中排除不可行的方案。观察可知这样的方案一定是在剩下一个长度为的不下降序列时多删除了一个数。剩下长度为的不下降序列的方案数为，多删除的数有种选法，于是可知不可行的方案数为。
综上可知，。然后就可以统计答案了。

总复杂度。

Code

#include <bits/stdc++.h>
#define MAX_N 2000
#define P 1000000007
using namespace std;
typedef long long lnt;
template <class T> inline void read(T &x) {
    x = 0; int c = getchar(), f = 1;
    for (; !isdigit(c); c = getchar()) if (c == 45) f = -1;
    for (; isdigit(c); c = getchar()) (x *= 10) += f*(c-'0');
}
map <int, int> mp;
int n, m, a[MAX_N+5], b[MAX_N+5];
lnt f[MAX_N+5][MAX_N+5], g[MAX_N+5], ans;
lnt tr[MAX_N+5][MAX_N+5], pw[MAX_N+5] = {1};
void add(int id, int p, lnt x) {for (; p <= m; p += (p&-p)) (tr[id][p] += x) %= P;}
lnt sum(int id, int p) {lnt ret = 0; for (; p; p -= (p&-p)) (ret += tr[id][p]) %= P; return ret;}
int main() {
    read(n);
    for (int i = 1; i <= n; i++) pw[i] = pw[i-1]*i%P;
    for (int i = 1; i <= n; i++) read(a[i]), b[i] = a[i];
    sort(b+1, b+n+1), m = (int)(unique(b+1, b+n+1)-b-1);
    for (int i = 1; i <= m; i++) mp[b[i]] = i;
    for (int i = 1; i <= n; i++) a[i] = mp[a[i]];
    f[0][0] = 1, add(0, 1, 1);
    for (int i = 1; i <= n; i++)
        for (int j = i; j; j--)
            f[i][j] = sum(j-1, a[i]), 
            (g[j] += f[i][j]) %= P, 
            add(j, a[i], f[i][j]);
    for (int i = 1; i <= n; i++)
        (ans += pw[n-i]*g[i]%P) %= P, 
        (ans += P-pw[n-i-1]*g[i+1]%P*(i+1)%P) %= P;
    return printf("%lld\n", ans), 0;
}